import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
//软件2201赵钧皓0304220126
public class project2 {

    // 动态规划解法，求解0-1背包问题，并输出最优解的物品
    public static int knapsack(int W, int n, int[] weights, int[] values, List<Integer> selectedItems) {
        // dp数组表示每个背包容量下的最大价值
        int[] dp = new int[W + 1];

        // 记录选择物品的状态，数组记录的是物品的索引
        boolean[][] chosen = new boolean[n + 1][W + 1];

        // 遍历所有物品
        for (int i = 1; i <= n; i++) {
            // 遍历背包容量从大到小更新dp数组，防止重复使用同一个物品
            for (int w = W; w >= weights[i - 1]; w--) {
                // 如果放入当前物品可以得到更大的价值
                if (dp[w] < dp[w - weights[i - 1]] + values[i - 1]) {
                    dp[w] = dp[w - weights[i - 1]] + values[i - 1];
                    chosen[i][w] = true; // 记录选择了物品i
                }
            }
        }

        // 反向追溯最优解
        int remainingWeight = W;
        for (int i = n; i > 0; i--) {
            if (chosen[i][remainingWeight]) {
                selectedItems.add(i);  // 记录被选中的物品
                remainingWeight -= weights[i - 1];  // 更新剩余背包容量
            }
        }

        // dp[W]表示背包最大容量W下的最大价值
        return dp[W];
    }

    public static void main(String[] args) {
        // 创建Scanner对象来读取用户输入
        Scanner scanner = new Scanner(System.in);

        // 读取背包的最大承重
        System.out.print("请输入背包的最大承重W: ");
        int W = scanner.nextInt();

        // 读取物品数量
        System.out.print("请输入物品的数量n: ");
        int n = scanner.nextInt();

        // 读取物品的重量和价值
        int[] weights = new int[n];
        int[] values = new int[n];

        System.out.println("请输入每个物品的重量和价值：");
        for (int i = 0; i < n; i++) {
            System.out.print("物品 " + (i + 1) + " 的重量: ");
            weights[i] = scanner.nextInt();
            System.out.print("物品 " + (i + 1) + " 的价值: ");
            values[i] = scanner.nextInt();
        }

        // 创建列表记录选择的物品
        List<Integer> selectedItems = new ArrayList<>();

        // 调用knapsack方法计算背包的最大价值，并获取最优解的物品
        int maxValue = knapsack(W, n, weights, values, selectedItems);

        // 输出结果
        System.out.println("背包的最大价值是: " + maxValue);
        System.out.println("最优解中选择的物品是：");
        for (int i = selectedItems.size() - 1; i >= 0; i--) {
            System.out.println("物品 " + selectedItems.get(i) + " (重量: " + weights[selectedItems.get(i) - 1] + ", 价值: " + values[selectedItems.get(i) - 1] + ")");
        }

        // 关闭Scanner对象
        scanner.close();
    }
}
